package Algorithm.UnionSet;

import java.util.HashSet;
import java.util.Set;

//https://leetcode-cn.com/problems/battleships-in-a-board/
//419. 甲板上的战舰
public class Leetcode419 {
    class Solution {
        private int[] fa;
        int[] vx = {0,-1,0,1,0};
        int[] vy = {-1,0,1,0,0};
        private Set<Integer> set;

        public int countBattleships(char[][] board) {
            init(board.length, board[0].length);
            set = new HashSet<Integer>();
            for(int i=0;i<board.length;i++){
                for(int j=0;j<board[0].length;j++){
                    if('X'==board[i][j]){
                        for(int k=0;k<5;k++){
                            int newX = i + vx[k];
                            int newY = j + vy[k];
                            if(newX>=0&&newX<board.length&&newY>=0&&newY<board[0].length&&'X'==board[newX][newY]){
                                int father = find(newX*board[0].length + newY);
                                if(!set.contains(father)){
                                    set.add(father);
                                }
                                fa[i*board[0].length+j] = father;
                                break;
                            }
                        }
                    }
                }
            }

            return set.size();
        }

        public void init(int m, int n){
            fa = new int[m*n];
            for(int i=0;i<fa.length;i++){
                fa[i] = i;
            }
        }

        public int find(int x){
            if(x == fa[x])
                return fa[x];
            return find(fa[x]);
        }
    }
}
